A switching network is comprised of ports with pins, conductors and switches. The ports and pins are external constructs of the switching network where each port contains a plurality of pins to interface to other switching networks or circuits. The conductors and switches are internal constructs of the switching network configured to transfer data or signals from pins of a first plurality of ports to pins of a second plurality of ports of the switching network. The pins of the first plurality of ports receive data or signals and transmit those data or signals through the conductors and the switches of the switching network to the pins of the second plurality of ports. The switching network can be bi-directional and in this case the pins of the first plurality of ports and the second plurality of port can both receive and transmit data or signals through the conductors and switches of the switching network. The pins of the ports of the switching network are physically connected to respective conductors of the switching network. The switches of the switching network can be programmed, either one time or repeatedly, to enable connection paths among the pins of the first plurality of ports to the pins of the second plurality of ports. The connection paths connecting pins inside the switching network can sometimes involve one or more intermediate conductors coupled through switches of the switching network.
Generally, the transmission of data or signals from the first plurality of ports to the second plurality of ports through the switching network can either be single-casting, where a pin of the first plurality of ports connects to a pin of the second plurality of ports, or can be multi-casting where data or signals of a pin of the first plurality of ports are transmitted to multiple pins of respective multiple ports of the second plurality of ports. The switching network can be used in an interconnection fabric for systems, networks and routers, etc, it can also be used as programmable interconnect circuitry for programmable logic circuits. In the case of programmable logic circuits, the multicasting corresponds to a source (output) connecting to multiple sinks (inputs) which is generally expressed as the fan-out of an output or fan-in of the inputs. For ease of illustration and consistency with the conventional way to describe such technologies, each switching network under discussion is denoted as having a first set of m conductors (having m number of conductors, for example) connecting to the pins of the first plurality of ports of the switching network. Without loss of generality, the first plurality of ports can be illustrated by a first port with m number of pins. The second plurality of ports is denoted as having k ports where each of the k ports has at most n number of pins. Additionally, there are n sets of conductors where each of the n sets of conductors having at most k number of conductors. Thus the switching network can be used to connect the pins of the first port to the pins of the k ports through use and control of switches and conductors of the switching network. Each pin of the first port is capable of connecting to at least one pin to each of the k ports through the switching network. Typically, multiple numbers of pins of the first port can independently connect to the pins of the k ports using the switching network without blocking.
FIG. 1 illustrates a conventional j-stage switching network (the “j-SN”) 1, where j is an integer, as described by Pani et al. (U.S. Pat. No. 6,975,139; hereinafter, “Pani”). The j-SN 1 has a first port 101 having m number of pins which are physically connected or coupled to the m conductors 10. Each of the k ports 102-108 has up to n=(n1× . . . ×nj) number of pins which are physically connected or coupled to the conductors of respective n plurality of at most k number of conductors 161 (112, 113, . . . , 117, 118); (122, 123, . . . , 127, 128); . . . ; and 163 (142, 143, . . . , 147, 148). Functional Blocks 102, 103, . . . , 107, 108 FB(i) for i=[1:k] represents either a set of lower level switching networks connecting to the j-SN of FIG. 1 or a set of circuit blocks connecting to the j-SN. Each of the ports 102, 103, 107 and 108 of FIG. 1 can be considered as the first port of the corresponding FB(i)'s.
Referring to FIG. 1, the m conductors (the first conductors) 10 are divided to form n1 sets of overlapping conductors each one having A number of conductors of 10 for A ranging between (m−n1+1) to m. The n1 sets of first conductors 11 through 12 can be configured to selectively couple an intermediate set of conductors having i1 number of conductors (the second conductors) for i1 ranging between m and (k×n). The i1 number of conductors are divided into n1 non-overlapping sets of second conductors, each set having approximately i1/n1 number of conductors corresponding to 15 through 16 of FIG. 1. Each of the n1 sets of first conductors 11 through 12 are coupled to a corresponding set of second conductors 15 through 16 through a corresponding sets of switches 13 through 14 each having A number of switches for s1(i) where i=[1:n1].
The conductors 15 are divided into n2 sets of overlapping conductors 105, . . . , 115, where each set has B number of conductors for B ranges between [i1/n1−n2+1: i1/n1]. In the embodiment of FIG. 1, each of the B number of conductors 105 are configured to selectively couple a next set of conductors 145 which is a non-overlapping subset of i2 number of conductors through a switch box 125 s2(1,1) having B number of switches. The i2 number of conductors (the third conductors) has between i1 number of conductors and (k×n) number of conductors which are divided into (n1×n2) sets of non-overlapping sets of conductors 145, . . . , 155, . . . , 146, . . . , 156 as illustrated in FIG. 1, the number of conductors in each of the (n1×n2) sets of non-overlapping conductors of i2 number of conductors 145, 155, 146, 156 etc. is approximately i2/n1/n2. Similarly, conductors 16 are divided into n2 sets of overlapping conductors 106, . . . , 116 which in turn couple, through respective sets of switches 126, . . . , 136 to n2 sets of non-overlapping conductors 146, . . . , 156.
Thus a parental set of i1/n1 number of second conductors 15 are divided into n2 sets of overlapping conductors each having between (i1/n1−n2+1) to i1/n1 number of conductors where each of the n2 sets of parental conductors (105, . . . , 115) couples, through a set of switches 125 having between (i1/n1−n2+1) to i1/n1 number of switches, to a set of child conductors 145 having approximately i2/n1/n2 number of third conductors. The children conductors (145, . . . , 155), (146, . . . , 156) are consisted of (n1×n2) sets of non-overlapping conductors having approximately i2/n1/n2 conductors in each of the (n1×n2) sets. The process described above can continue for the j-SN 1 when j is greater than two.
Referring to FIG. 1, there are (n1× . . . ×nj) number of non-overlapping sets of C number of conductors 110, . . . , 120, . . . 130, . . . , 140 as the last j stages of intermediate conductors in the j-SN 1, where C=ij/n1/ . . . /nj for ij ranging between i(j−1) and (k×n) where i(j−1) is the number of conductors of the parental conductors and ij is the children conductors for j greater than two. Each set of the C number of conductors such as the first set 110 is configured to selectively couple, through switches 111 which has (C×k) number of switches, to k number of conductors 112, 113, . . . , 117, 118 which are physically connected to k pins in each of the k ports (as pin 1 in ports 102, . . . , 103, . . . , 107, . . . , 108 of 161) having up to n number of pins in each port. Each of the k ports is either associated with another switching network or a functional block.
In the case of j=1, i.e., 1-SN, conductors 15 would be represented by the first set of conductors 110 of FIG. 1 while the parental sets of conductors (105, . . . , 115, . . . , 106, 116) through (145, . . . , 155, . . . , 146, . . . , 156) do not exist. Additionally, there are only n1 sets of conductors of the type represented by the first set of conductors 110 and respective number of sets of switches represented by the switches 111 in this case.
In the case of 2-SN, the types of conductors 145 would be represented by the first set of conductors 110 of FIG. 1, so there are only (n1×n2) sets of conductors 110 types of conductors and ditto sets of switches represented by switches 111.
In the physical implementation of a switching network onto an integrated circuit, there are trade-offs in terms of layout efficiency. Typically, switches are larger than wires or conductors in terms of area. With present processing manufacturing technology, it is not yet practical to stack devices on top of each other in an integrated circuit but it is possible to allow conductors to be implemented in multiple layers of interconnections on top of the area occupied by switches. Thus, one can investigate the relationships between the numbers of switches versus the numbers of conductors in a switching network to achieve an efficient layout implementation in an integrated circuit. Ideally, if the conductors can be implemented within the area occupied by the switches, then there is little area wasted; hence, the implementation can be considered optimum for the integrated circuit. Area minimization in layout implementation is important both for manufacturing cost and speed considerations. Thus, it is important to consider the layout efficiency of the switching network while implementing an interconnection fabric.